class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        stT = {}
        stS = {}
        for i in range(len(t)):
            tItem = t[i]
            if tItem in stT:
                stT[tItem] += 1
            else:
                stT[tItem] = 1
            if i < len(t) - 1:
                sItem = s[i]
                if sItem in stS:
                    stS[sItem] += 1
                else:
                    stS[sItem] = 1
        
        for k in stT:
            if k not in stS or stT[k] != stS[k]:
                return k

    def findTheDifference2(self, s: str, t: str) -> str:
        from collections import Counter
        k = Counter(t) - Counter(s)
        return list(k.keys())[0]

    def findTheDifference3(self, s: str, t: str) -> str:
        n = len(s)
        s = list(s)
        s.sort()
        t = list(t)
        t.sort()
        for i in range(n):
            if s[i] == t[i]:
                continue
            else:
                return t[i]
        return t[n]